package dynamicprogramming

/*
1、动态规划理论基础
day:2022-6-17

动态规划，英文：Dynamic Programming，简称DP.
如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，
这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的.

大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
1-确定dp数组（dp table）以及下标的含义
2-确定递推公式
3-dp数组如何初始化
4-确定遍历顺序
5-举例推导dp数组
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？

因为一些情况是递推公式决定了dp数组要如何初始化！

动态规划应该如何debug:
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。


动态规划是一个很大的领域，今天这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础!
注意这里不是说不让大家问问题哈， 而是说问问题之前要有自己的思考，比如先尝试自己调debug,
然后再针对性问问题，这样可以问到点子上！

大家工作之后就会发现，特别是大厂，问问题是一个专业活，是的，问问题也要体现出专业！
*/
